Arithmetic operations are used within many types of computing system, and can often represent a key part of the processing being performed by the system. For this reason, efficient mechanisms for carrying out various types of mathematical operation are sought, and because of the very large numbers of operations carried out by some computing systems it is possible for quite modest improvements in the efficiency of such mechanisms to produce very significant performance improvements overall. These mechanisms can be implemented in electronic circuitry, and incorporated into the microprocessors used in central processing units or auxiliary numeric processors in computing systems. These mechanisms can also be implemented in software, in which case the programming language used makes available the basic operations which a processor is able to carry out.
FIG. 1 shows a typical numeric processor mechanism found in computing systems. This mechanism comprises: (1) a sequence of instructions, which may be incorporated into the design of the mechanism but are more commonly supplied to the mechanism in the form of an executable program of instructions; (2) an instruction pointer, which indicates which instruction is to be processed next; (3) a processor which incorporates a range of basic numeric operations, and which is capable of reading the instruction at the instruction pointer and processing it; (4) some local storage in which can be stored the values which the numeric processor is working on, and the results of the operations it carries out. The types of instruction which can be included in the sequence of instructions (1) will vary from device to device, but typically include some instructions for loading particular values into the numeric registers (4), some instructions for performing operations on one or more values in the numeric processor (3), and some instructions which can modify the instruction pointer (2) in order to enable branching and looping within the sequence of instructions.
Arithmetic operations within computing systems are typically carried out by numeric processors operating with binary (base 2) arithmetic. Base 2 arithmetic is well adapted for implementing in electronic circuitry or in microprocessor designs. However, base 2 arithmetic is poorly adapted to modelling many users' applications of arithmetic, both because users are not accustomed to supplying or interpreting base 2 values and also because certain precision and rounding behaviours which occur in traditional base 10 arithmetic are difficult to model in base 2. Therefore, modern computing systems are increasingly required to perform conversions between the base 2 representations used internally and the base 10 representations used by the users, and to simulate the performing of arithmetic operations in base 10 while still using a base 2 arithmetic unit.
Values represented in base 10 can readily be converted to base 2 with a sequence of integer multiplication and additions, which are relatively rapid operations, and this can be carried out efficiently by a mechanism such as that shown in FIG. 1. However, converting a value represented in base 2 to a representation in base 10 normally requires integer division (including collection of the remainder) of values by 10, or by various powers of 10 depending on the representation being used. General integer division is a relatively lengthy process, even when the numeric processor's arithmetic unit provides a suitable integer division operation which can be used directly. It is not uncommon for a general integer division operation to take in excess of forty times as long as an addition operation.
Implementors of arithmetic computing systems have therefore sought methods for performing particular division operations in more rapid ways. Division by a power of 2 is normally a trivial and very rapid operation on a base 2 arithmetic numeric processor. Methods for performing divisions by other values have also been devised. They are known to one skilled in the art, and are described in the relevant literature.
FIG. 2 illustrates such a method to perform the integer division of an integer value. In FIG. 2 and elsewhere in this document, the following notation is used:                ceil (x) denotes the smallest integer greater than or equal to x        floor (x) denotes the largest integer less than or equal to x        x+y denotes x plus y        x−y denotes x minus y        x*y denotes x multiplied by y        x/y denotes x divided by y        x DIV y denotes the result of the integer division of x by y, equal to floor (floor(x)/floor(y))        x^y denotes x raised to the power y for a non-negative integer y        log2(x) denotes the logarithm to base 2 of x for x>=1, i.e. the value y for which x=2^log2(y)        
The method of FIG. 2 accomplishes the division by multiplying the integer value by an integer factor and then dividing the result by a power of 2 (i.e. 2^A). Both of these operations are rapid, so the method is generally effective. However, the result is only accurate for a certain range of input values X and integer values A. In general, the larger the value chosen for A, the greater the range of input values X for which the correct result Q is generated, but also the greater the value of the intermediate result (X*F) and thus The larger the numeric register required to apply the method. If the size of the numeric register is subject to a fixed limit, as is often the case, and the intermediate results are to be accommodated within the register, then this limits the size of the value which can be chosen for A. To apply this method successfully, the best value of A must be chosen for the needs of the application. For example, when D is 10, and choosing A to be 19, this method can correctly divide all 16-bit base 2 (unsigned) values by 10, performing the calculation in a 32-bit base 2 (unsigned) numeric register.
However, a method such as that shown in FIG. 2 becomes unusable when it is impossible to reconcile the competing requirements of extending the range of input values for which the method is accurate while being able to perform the calculation in a certain size of numeric register. This becomes a particularly difficult problem to avoid when attempting to devise methods to perform integer divisions by large divisors.